这道题显然是最短路,但是似乎转向时不好处理,于是我们要用到分层图。
实现很简单,建立两层图,第一层记录横向边,第二层记录纵向边,相同的关键点两层图连一条费用为1的边。
还有,这道题只需要在关键点之间连边(非关键点无法转向,连了也没用),路径长度为坐标差*2。
对于起点和终点,我们把它也当作关键点,但转向只需0的费用。
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXM = 100005;
int n , m;
struct Point{
int x , y , id;
}imp[ MAXM + 5 ];
bool cmpx( const Point &a , const Point &b ) {
return a.x < b.x || ( a.x == b.x && a.y < b.y );
}
bool cmpy( const Point &a , const Point &b ) {
return a.y < b.y || ( a.y == b.y && a.x < b.x );
}
bool cmpi( const Point &a , const Point &b ) {
return a.id < b.id;
}
struct node{
int v , w;
bool operator > ( const node &x ) const {
return w > x.w;
}
};
vector< node > Graph[ 8 * MAXM + 5 ];
int dist[ 2 * MAXM + 5 ];
bool vis[ 2 * MAXM + 5 ];
int Dijkstra( int s , int t ) {
priority_queue< node , vector< node > , greater< node > > Que;
memset( dist , INF , sizeof( dist ) );
memset( vis , 0 , sizeof( vis ) );
Que.push( { s , dist[ s ] = 0 } );
while( !Que.empty( ) ) {
int u = Que.top( ).v; Que.pop( );
if( vis[ u ] ) continue;
vis[ u ] = 1;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ].v , w = Graph[ u ][ i ].w;
if( dist[ v ] > dist[ u ] + w ) {
dist[ v ] = dist[ u ] + w;
Que.push( { v , dist[ v ] } );
}
}
}
return dist[ t ] == INF ? -1 : dist[ t ];
}
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= m ; i ++ )
scanf("%d %d", &imp[ i ].x , &imp[ i ].y ) , imp[ i ].id = i;
m ++ , scanf("%d %d", &imp[ m ].x , &imp[ m ].y ) , imp[ m ].id = m;
m ++ , scanf("%d %d", &imp[ m ].x , &imp[ m ].y ) , imp[ m ].id = m;
sort( imp + 1 , imp + m + 1 , cmpx );
for( int i = 1 ; i <= m ; i ++ ) {
int dex1 = imp[ i ].id , dex2 = imp[ i + 1 ].id;
if( imp[ i ].x != imp[ i + 1 ].x ) continue;
Graph[ dex1 ].push_back( { dex2 , 2 * ( imp[ i + 1 ].y - imp[ i ].y ) } );
Graph[ dex2 ].push_back( { dex1 , 2 * ( imp[ i + 1 ].y - imp[ i ].y ) } );
}
sort( imp + 1 , imp + m + 1 , cmpy );
for( int i = 1 ; i <= m ; i ++ ) {
int dex1 = imp[ i ].id + MAXM , dex2 = imp[ i + 1 ].id + MAXM;
if( imp[ i ].y != imp[ i + 1 ].y ) continue;
Graph[ dex1 ].push_back( { dex2 , 2 * ( imp[ i + 1 ].x - imp[ i ].x ) } );
Graph[ dex2 ].push_back( { dex1 , 2 * ( imp[ i + 1 ].x - imp[ i ].x ) } );
}
sort( imp + 1 , imp + m + 1 , cmpi );
for( int i = 1 ; i <= m ; i ++ ) {
int f = ( i <= m - 2 ) , dex1 = imp[ i ].id , dex2 = imp[ i ].id + MAXM;
Graph[ dex1 ].push_back( { dex2 , f } );
Graph[ dex2 ].push_back( { dex1 , f } );
}
printf("%d", Dijkstra( m - 1 , m ) );
return 0;
}